package com.ai.zuochengyun.phase01.class03;

/**
 * 是否是平衡二叉树
 */
public class Code19_IsBalanceTree {

    public static void main(String[] args) {
        BinaryTreeNode head = new BinaryTreeNode(1);
        head.left = new BinaryTreeNode(2);
        head.right = new BinaryTreeNode(3);
        head.left.left = new BinaryTreeNode(4);
        head.left.right = new BinaryTreeNode(8);
        head.right.left = new BinaryTreeNode(5);
        head.right.right = new BinaryTreeNode(6);

        Info info = process(head);
        System.out.println(info.isBalanced);
    }

    public static Info process(BinaryTreeNode head) {
        if (head == null) {
            return new Info(true, 0);
        }

        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        boolean isBalanced = true;
        // 左树是不是平衡的
        if (!leftInfo.isBalanced) {
            isBalanced = false;
        }
        // 右树是不是平衡的
        if (!rightInfo.isBalanced) {
            isBalanced = false;
        }
        // 左右树的高度差是否小于2
        if (Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isBalanced = false;
        }
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        return new Info(isBalanced, height);
    }

    public static class Info {
        public boolean isBalanced;

        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }
}
